package LeetCode.month03.day65;

import java.util.Arrays;

/**
 * @author 16778
 * @version 1.0
 * @date 2025/9/29 7:59
 */
public class No1039 {
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        int[][] dp = new int[n][n];
        for (int[] ints : dp) {
            Arrays.fill(ints,-1);
        }
        return deep(0,n-1,values,dp);
    }

    private int deep(int l, int r, int[] values,int[][]memo) {
        if(l+1==r)
            return 0;
        if(memo[l][r]!=-1)
            return memo[l][r];
        int res = Integer.MAX_VALUE;
        for (int i = l+1; i < r; i++) {
            res = Math.min(deep(l,i,values,memo)+deep(i,r,values,memo)+values[l]*values[r]*values[i],res);
        }
        return memo[l][r] = res;
    }
}
